package leetcode_1000;

/**
 * @author 周杨
 * 2018年11月18日 下午1:20:21 求一个数组最大连续子数组的和 可以是循环形式的连续子数组
 * MaximumSumCircularSubarray_918_.java
 * description:分两种形式 用Kadane算法实现 AC 30%
 */
public class MaximumSumCircularSubarray_918_ {
	public static void main(String[] args) {
		MaximumSumCircularSubarray_918_ test=new MaximumSumCircularSubarray_918_();
		System.out.println(test.maxSubarraySumCircular(new int[] {5,-3,5}));
	}
	
	public int maxSubarraySumCircular(int[] A) {
		int sum=0;
		int max=Integer.MIN_VALUE;
		for(int i:A) {
			sum+=i;
			max=Math.max(max, i);
		}
		if(max<0)
			return max;//全是负数
		return Math.max(max(A), sum-min(A));
    }
	
	public int max(int [] nums) {
		int add = nums[0];
        int total = nums[0];
        for(int i=1; i<nums.length; i++){
            add = Math.max(nums[i], nums[i] + add);
            total = Math.max(add, total);
        }
        return total;
	}
	
	
	public int min(int [] nums) {
		int add = nums[0];
        int total = nums[0];
        for(int i=1; i<nums.length; i++){
            add = Math.min(nums[i], nums[i] + add);
            total = Math.min(add, total);
        }
        return total;
	}
}
